package LeetCode._02算法基础.day02二分查找;

import org.junit.Test;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 12 - 8:54
 * @Description nums原来是一个升序排列的数组，进行了多次旋转。请你找出并返回数组中的最小元素
 * @Version 中等
 */
public class _153旋转数组最小值 {
    static int[] nums = {3, 4, 5, 1, 2};

    @Test
    public void solve() {
        int res = findMin(nums);
        System.out.println(res);
    }

    /*by me 二分查找*/
    public int findMin(int[] nums) {
        //取第一个元素为最小值
        int min = nums[0];
        int left = 0, right = nums.length - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] >= nums[0]) {//mid 左边升序
                //已经取了其最小值，向右
                left = mid + 1;
            } else { //mid 右边升序
                //取其最小值，向左
                min = Math.min(min, nums[mid]);
                right = mid - 1;
            }
        }
        return min;
    }

    /*官方思路*/
    public int findMin1(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;

            if (nums[pivot] < nums[high]) { //pivot右边升序
                high = pivot;//取右边最小的
            } else {    //pivot右边存在最小值
                low = pivot + 1;
            }
        }
        //最后 low 指向最小值
        return nums[low];
    }

}
